Computers are finding new and useful applications in the quasi-intelligent areas of making predictions, and recognizing patterns and objects. Brief consideration of how the human brain makes predictions or estimates based on incomplete information reveals how numerous and varied the useful applications for such a capacity are. This is, in many cases, because computers can take in and process large amounts of the most tedious information round the clock to provide valuable intelligence that can be used to augment or supplement human decisions and provide automated control and information. Such computer implemented methods and systems go by various popular names such as inference engines, pattern recognition, artificial intelligence, etc.
The mathematical basis for making these kinds of estimates often leads to extremely complex problems which are hard to solve in a reasonable time on a computer. One kind of estimate is called a Bayesian inference, which is a statistical inference based on evidence, descriptive data, or observations that are combined to infer the probability of an event or object or other thing that can be inferred from the data. The more data, the more reliable the inference. With large amounts of data and many conditions defining interrelationships among them, many Bayesian inferences of practical importance take a long time on computers. There is a perennial need to find more efficient ways to process such problems to permit new applications of such computer implemented technology.
In Bayesian statistics, the posterior probability of an event or other thing is the conditional probability estimate in view of all evidence. Many useful problems seek the most likely configuration of a system, or a best estimate from the posterior probabilities called maximum a posteriori (MAP) estimate. The system is usually described by a Bayesian network. When the configuration is discrete, estimations can be NP hard, that is, answers can be verified quickly, and a quick algorithm to solve the problem can solve other NP problems quickly. Many problems have been solved using message passing or belief propagation techniques, which can be efficiently implemented on computers. However, there is a need for ensuring and determining the exactness of these methods.